CF1536F
[为啥我只会做简单题...好难受...呜, 菜死了呜]
题目难度: 省选- [CF2200]
题目分类: 组合数学/博弈论
题目大意: (CF1536F)
珂朵莉和威廉在去到了地表世界!
威廉决定和珂朵莉玩一个游戏,
"有一个长度为 n 的环型棋盘"
"我们轮流在棋盘上放上棋子, 我先放"
"但你的棋子, 不能和我的棋子相邻"
"但我的棋子, 也不能和你的棋子相邻"
"最后无法操作的人的就是败者"
珂朵莉很想让威廉赢, 所以她想知道如果双方都采用最优策略, 一共会有多少种不同的棋局?
棋局相同, 当且仅当结束场面相同同时过程相同
\(n ≤ 10^6\)
解题思路:
过于神秘, 无法评价
但不要局限在思维定式当中
考虑这种问法说明不存在唯一必胜策略
那么一定存在多种必胜策略, 或者没有必胜策略
跳跃性的猜想, 珂朵莉多种存在必胜策略, 后证明即可
题目答案:
Claim: 珂朵莉无论如何都会胜利
无论如何, 即任何操作都是必胜策略, 威廉任何操作都是必负策略
若结束场面忽视棋盘中空的位置, 必然是ABABABAB交替
其中每个缝隙, 即AB和BA之间的位置, 都可能存在一个空位置
第一个A和最后一个B之间也有可能存在
断环为链, 分类讨论链首的状态即可
综上, 显然, 答案为:
\[ 2\sum_{i=1}^{\lfloor \frac{n}{2} \rfloor} (2i)!\binom{2i}{n-2i} +(2i)!\binom{2i-1}{n-2i-1} \]
时间复杂度为 \(O(n)\)
Prove:
反证法, 若珂朵莉负, 则结束场面的棋盘中应是 ABABAB....ABABA
但由于首尾都是A, 则必然之间存在一个空位, 则可以珂朵莉将棋子放到该位置, 则珂朵莉胜, 矛盾 \(\square\)